# This is a sample Python script.

# Press Shift+F10 to execute it or replace it with your code.
# Press Double Shift to search everywhere for classes, files, tool windows, actions, and settings.
from typing import List


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        # 当前连续最大值
        # 和最大值
        current_num_max = num_max = nums[0]

        for i in range(1, n):
            current_num_max = max(nums[i], current_num_max + nums[i])
            num_max = max(num_max, current_num_max)
        return num_max

    # Press the green button in the gutter to run the script.


if __name__ == '__main__':
    nums = [5, 4, -1, 7, 8]
    solution = Solution()
    print(solution.maxSubArray(nums))

# See PyCharm help at https://www.jetbrains.com/help/pycharm/
